Hóa thạch chủ yếu của C. megalodon là răng và cột sống.[5] Giống mọi loài cá mập, bộ xương C. megalodon được cấu tạo từ sụn chứ không phải xương thông thường; điều này làm các mẫu vật bị bảo quản rất tệ.[12] Dù những dấu vết cổ nhất của megalodon có niên đại từ các địa tầng thế Oligocen muộn, khoảng 28 triệu năm trước,[13][14] thường thì người ta cho rằng loài này bắt đầu xuất hiện vào thế Miocen giữa, chừng 15.9 triệu năm trước.[1] Mặc dù các địa tầng kéo dài khỏi biên giới Phân đại Đệ Tam thường thiếu vắng hóa thạch megalodon,[5] nhưng chúng đã được báo cáo có mặt trong các địa tàng thế Pleistocen sau đó.[15] C. megalodon tuyệt chủng vào cuối thế Pliocen, có thể khoảng 2.6 triệu năm trước;[1] răng C. megalodon thời kỳ sau Pliocen được cho là hóa thạch giả.[12] C. megalodon có phạm vi phân bố toàn cầu, hóa thạch được khai quật tại nhiều nơi trên thế giới, gồm châu Âu, châu Phi, cả Bắc và Nam Mỹ,[5][7] cũng như Puerto Rico,[16] Cuba,[17] Jamaica,[18] quần đảo Canary,[19] Úc,[20] New Zealand,[21] Nhật Bản,[5][7] Malta,[21] Grenadines[22] và Ấn Độ.[7] Răng megalodon đã được tìm thấy tại các vùng đất rất xa bờ, như rãnh Mariana ở Thái Bình Dương.[21]

Hóa thạch megalodon phổ biến nhất là răng. Các đặc điểm là: dạng hình tam giác,[2] cấu trúc thẳng,[5] kích thước lớn,[2] có răng cưa dọc các rìa.[2] Megalodon có răng to nhất trong tất cả các loài cá mập được biết đến.[21]

Vài hóa thạch cột sống đã được tìm thấy.[7] Nổi bật nhất là cột sống được bảo quản một phần của một cá thể, khai quật tại Antwerp, Bỉ bởi M. Leriche năm 1926. Nó gồm 150 đốt sống trung tâm, đường kính mỗi đốt từ 55 milimét (2,2 in) tới 155 milimét (6,1 in).[5] Tuy nhiên, các nhà khoa học cho rằng có thể có đốt sống còn lớn lớn.[5] Cột sống được bảo quản một phần của một cá thể khác đã được tìm ra tại Gram clay, Đan Mạch bởi Bendix-Almgeen năm 1983. Mẫu vật này gồm 20 đốt sống, đường kính mỗi đốt từ 100 milimét (3,9 in) tới 230 milimét (9,1 in).[23]